/**********************************************************************
 * file:  sr_router.c
 * date:  Mon Feb 18 12:50:42 PST 2002
 * Contact: casado@stanford.edu
 *
 * Description:
 *
 * This file contains all the functions that interact directly
 * with the routing table, as well as the main entry method
 * for routing.
 *
 **********************************************************************/

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <netinet/in.h>
#include <time.h>

#include "sr_if.h"
#include "sr_rt.h"
#include "sr_router.h"
#include "sr_protocol.h"


/*---------------------------------------------------------------------
 *  Method: sr_init(void)
 * Scope:  Global
 *
 * Initialize the routing subsystem
 *
 *---------------------------------------------------------------------*/

void sr_init(struct sr_instance* sr)
{

	/* REQUIRES */
	assert(sr);

	/* Add initialization code here! */
	unsigned int i;
	uint32_t emptyHostName = 0;
	struct sr_arp_cache_entry *emptyARPCacheEntry;
	emptyARPCacheEntry = (struct sr_arp_cache_entry *)malloc(sizeof(struct sr_arp_cache_entry));
	assert(emptyARPCacheEntry);
	emptyARPCacheEntry->arp_addr = 0;
	emptyARPCacheEntry->arp_age = 0;
	for(i = 0; i < ETHER_ADDR_LEN; i = i + 1)
	{
		emptyARPCacheEntry->arp_dha[i] = 0xff;
	}

	for(i = 0; i < MAX_HOSTS; i = i + 1)
	{
		sr->cacheHosts[i] = emptyHostName;
		sr->timers[i] = 0;
		sr->packetsSinceAck[i] = 0;
		sr->arp_cache[i] = emptyARPCacheEntry;
		int j;
		for(j = 0; j < CACHE_SIZE; j++)
		{
			sr->packetCacheEntryStatus[i][j] = 0;
		}
	}

} /* -- sr_init -- */


/*---------------------------------------------------------------------
 * Method: sr_handlepacket(uint8_t* p,char* interface)
 * Scope:  Global
 *
 * This method is called each time the router receives a packet on the
 * interface.  The packet buffer, the packet length and the receiving
 * interface are passed in as parameters. The packet is complete with
 * ethernet headers.
 *
 * Note: Both the packet buffer and the character's memory are handled
 * by sr_vns_comm.c that means do NOT delete either.  Make a copy of the
 * packet instead if you intend to keep it around beyond the scope of
 * the method call.
 *
 *---------------------------------------------------------------------*/

void sr_handlepacket(struct sr_instance* sr, uint8_t *packet, unsigned int len, char *interface)
{

	struct sr_ethernet_hdr *eth_hdr;

	/* REQUIRES */
	assert(sr);
	assert(packet);
	assert(interface);
	printf("*** -> Received packet of length %d \n",len);
	/* handle ethernet type */
	eth_hdr = get_ethernet_hdr(packet);
	/*
	uint8_t type = (uint8_t)eth_hdr->ether_type;
	uint8_t leng = (uint8_t)(eth_hdr->ether_type >> 8);
	uint16_t new_type = ((uint16_t)type << 8);
	new_type = new_type + ((uint16_t)leng);
	eth_hdr->ether_type = new_type;
	set_ethernet_hdr(packet,eth_hdr);
	 */
	if(htons(eth_hdr->ether_type) == ETHERTYPE_IP)
	{
		struct ip *ip_hdr;
		Debug("ip packet recv'd\n");
		ip_hdr = get_ip_hdr(packet);
		if(htons(ip_hdr->ip_p) == IPPROTO_ICMP)
		{
			struct sr_icmphdr *icmphdr;
			Debug("icmp packet recv'd\n");
			icmphdr = get_icmp_hdr(packet);
			sr_handle_icmp_packet(sr, len, interface, icmphdr, packet);
			free(icmphdr);
		}
		else if(htons(ip_hdr->ip_p) == IPPROTO_TCP)
		{
			struct tcp *tcphdr;
			Debug("tcp packet recv'd\n");
			tcphdr = get_tcp_hdr(packet);
			sr_handle_tcp_packet(sr, len, interface, tcphdr, packet);
			free(tcphdr);
		}
		else if(htons(ip_hdr->ip_p) == IPPROTO_UDP)
		{
			struct sr_udphdr *udphdr;
			Debug("udp packet recv'd\n");
			udphdr = get_udp_hdr(packet);
			sr_handle_udp_packet(sr, len, interface, udphdr, packet);
			free(udphdr);
		}
		free(ip_hdr);
	}
	else if(htons(eth_hdr->ether_type) == ETHERTYPE_ARP)
	{
		struct sr_arphdr *arphdr;
		arphdr = get_arp_hdr(packet);
		Debug("arp packet recv'd\n");
		sr_handle_arp_packet(sr, len, interface, arphdr, packet);
		free(arphdr);
	}

	free(eth_hdr);
	/* Here I use the event of a packet arriving to take a packet out of every cache for each validated destination */
	/*
	int i;
	for(i = 0; i < MAX_HOSTS; i = i + 1)
	{
		bool isStale = test_staleness(sr, i);
		int ackResponsiveness = sr->packetsSinceAck[i];
		if(isStale || ackResponsiveness >= MAX_SEND_PACKET)
		{
			Debug("ARP packet cache has become stale or unresponsive\n");
			int j;
			int moreMessagesToBeSent = sr->packetCacheEntryStatus[i][0];
			for(j = 1; j < CACHE_SIZE && moreMessagesToBeSent == 1; j++)
			{
				uint8_t* currentPacket = sr->packetCache[i][j-1];
				struct sr_ethernet_hdr *eth_hdr;
				eth_hdr = get_ethernet_hdr(currentPacket);
				unsigned char dst_addr[ETHER_ADDR_LEN];
				int k;
				for(k = 0; k < ETHER_ADDR_LEN; k++)
				{
					dst_addr[k] = (unsigned char)(eth_hdr->ether_shost[k]);
				}
				struct in_addr dst;
				dst.s_addr = htonl(sr_get_host_ip_from_ether_addr(sr, dst_addr));
				uint8_t *error_packet = create_icmp_msg(sr, packet, sr->routing_table->gw, dst, IP_ICMP_LEN, interface, ICMP_TYPE_DEST_UNREACHABLE, ICMP_CODE_DEST_HOST_UNREACHABLE);
				sr_route_packet(sr, error_packet, len, interface);
				moreMessagesToBeSent = sr->packetCacheEntryStatus[i][j];
			}
			sr_handle_staleness(sr, i);
		}
		else
		{

		}

	}
	 */
}/* end sr_ForwardPacket */


/* Route packet */
void sr_route_packet(struct sr_instance *sr, uint8_t *packet, unsigned int len, char *interface)
{
	struct sr_ethernet_hdr *eth_hdr = get_ethernet_hdr(packet);

	/*
	uint8_t type = (uint8_t)eth_hdr->ether_type;
	uint8_t leng = (uint8_t)(eth_hdr->ether_type >> 8);
	uint16_t new_type = ((uint16_t)type << 8);
	new_type = new_type + ((uint16_t)leng);
	eth_hdr->ether_type = new_type;
	 */
	printf("ether header type = %x\n",htons(eth_hdr->ether_type));

	/* ARP packet */
	if(htons(eth_hdr->ether_type) == ETHERTYPE_ARP)
	{
		printf("Sending ARP packet\n");
		struct sr_arphdr *arp_hdr = get_arp_hdr(packet);
		struct sr_rt *entry;

		/*
		unsigned int dst = arp_hdr->ar_tip;
		unsigned int msk;
		unsigned int subnet;
		*/

		struct in_addr temp;
		temp.s_addr = arp_hdr->ar_tip;
		char *dst = inet_ntoa(temp);
		unsigned int msk;
		char *subnet;

		int i;
				struct sr_if *iface = sr_get_interface(sr, entry->interface);
		for(entry=sr->routing_table->next; entry!=NULL; entry=entry->next)
		{
			iface = sr_get_interface(sr, entry->interface);

			subnet = inet_ntoa(entry->dest);
			if(strcmp(subnet,dst)==0)
			{
				for(i=0; i<ETHER_ADDR_LEN; i++)
				{
					eth_hdr->ether_dhost[i] = eth_hdr->ether_shost[i];
					eth_hdr->ether_shost[i] = iface->addr[i];
				}
				/*eth_hdr->ether_type = 0x0806;*/
				memcpy(packet, eth_hdr, 14);

				arp_hdr->ar_tip = arp_hdr->ar_sip;
						/*arp_hdr->ar_sip = entry->gw.s_addr;*/

				/*arp_hdr->ar_sip = ntohl(iface->ip);*/

				arp_hdr->ar_sip = ntohl(iface->ip);
				arp_hdr->ar_tip = ntohl(arp_hdr->ar_tip);



				uint8_t type0 = *(packet + 8 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
				uint8_t	type1 = *(packet + 9 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
				uint8_t type2 = *(packet + 10 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
				uint8_t type3 = *(packet + 11 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
				uint32_t type0123 = ((uint32_t)type3 << 24) + ((uint32_t)type2 << 16) + ((uint32_t)type1 << 8) + ((uint32_t)type0);
				arp_hdr->ar_sip = type0123;


				set_arp_hdr(packet, arp_hdr);

				/*arp_hdr->ar_tip = entry->gw.s_addr;
				set_arp_hdr(packet, arp_hdr);*/
				sr_send_packet(sr, packet, len, entry->interface);
				return ;
			}
		}


		printf("no match\n");

		entry = sr->routing_table;

		struct in_addr dest_addr;
		inet_aton(dst, &dest_addr);
		char * shost_chr = get_hardware_address(sr, dest_addr);
		for(i=0; i<ETHER_ADDR_LEN; i++)
		{
			eth_hdr->ether_dhost[i] = eth_hdr->ether_shost[i];
			eth_hdr->ether_shost[i] = iface->addr[i];
		}
		eth_hdr->ether_type = 0x0806;
		memcpy(packet, eth_hdr, 14);

		arp_hdr->ar_tip = arp_hdr->ar_sip;
		/*arp_hdr->ar_sip = entry->gw.s_addr;*/

		arp_hdr->ar_sip = htonl(iface->ip);
		arp_hdr->ar_sip = htonl(arp_hdr->ar_sip);
		arp_hdr->ar_tip = htonl(arp_hdr->ar_tip);
		set_arp_hdr(packet, arp_hdr);

		sr_send_packet(sr, packet, len, entry->interface);

		return ;
	}

	/* IP packet */
	else if(htons(eth_hdr->ether_type) == ETHERTYPE_IP)
	{
		struct ip *ip_hdr = get_ip_hdr(packet);
		struct sr_rt *entry;
		unsigned int dst;
		unsigned int msk;
		unsigned int subnet;

		/* discard ip packet */
		if(ip_hdr->ip_ttl == 1)
		{
			uint8_t *p = create_icmp_msg(sr, packet, entry->gw, ip_hdr->ip_src, len, interface, ICMP_TYPE_DEST_UNREACHABLE, ICMP_CODE_DEST_HOST_UNREACHABLE);
			sr_send_packet(sr, p, len, interface);
			free(packet);
			return ;
		}

		dst = (unsigned int)inet_ntoa(ip_hdr->ip_dst);
		for(entry=sr->routing_table->next; entry!=NULL; entry=entry->next)
		{
			msk = (unsigned int)inet_ntoa(entry->mask);
			subnet = (unsigned int)inet_ntoa(entry->dest);

			/* matched routing table entry */
			if((dst & msk) == subnet)
			{
				/* arp cache array index for router interface
				int iEth = sr_get_cache_host_id(sr, entry->gw.s_addr);*/

				/* arp cache array index for destination interface */
				int iDst = sr_get_cache_host_id(sr, ip_hdr->ip_dst.s_addr);
				struct sr_if *iface = sr_get_interface(sr, entry->interface);

				/* destination mac address is not in the arp cache */
				/* create arp request */
				if(iDst == -1)
				{
					free(packet);
					packet = (uint8_t *)malloc(sizeof(struct sr_ethernet_hdr) + sizeof(struct sr_arphdr));
					assert(packet);

					/* reset ethernet header */
					int i;
					for(i=0; i<ETHER_ADDR_LEN; i++)
					{
						eth_hdr->ether_dhost[i] = 0xFF;
						eth_hdr->ether_shost[i] = iface->addr[i];
					}
					eth_hdr->ether_type = 0x0806;
					memcpy(packet, eth_hdr, 14);

					/* set arp header */
					struct sr_arphdr *arp_hdr = create_arp_hdr(ARP_REQUEST, eth_hdr->ether_shost, iface->ip, eth_hdr->ether_dhost, ip_hdr->ip_dst.s_addr);
					memcpy(packet+14, arp_hdr, sizeof(struct sr_arphdr));

					sr_send_packet(sr, packet, len, entry->interface);
					return ;
				}
				/* destination mac address is in the arp cache */
				else
				{
					struct sr_if *iface = sr_get_interface(sr, entry->interface);
					int i;
					for(i=0; i<ETHER_ADDR_LEN; i++)
					{
						eth_hdr->ether_dhost[i] = sr->arp_cache[iDst]->arp_dha[i];
						eth_hdr->ether_shost[i] = iface->addr[i];
					}
					eth_hdr->ether_type = 0x0008;
					memcpy(packet, eth_hdr, 14);

					ip_hdr->ip_ttl = ip_hdr->ip_ttl - 1;
					/*
					ip_hdr->ip_dst = ip_hdr->ip_src;
					struct in_addr temp;
					temp.s_addr = iface->ip;
					ip_hdr->ip_src = temp;
					*/
					set_ip_hdr(packet, ip_hdr);
					sr_send_packet(sr, packet, len, entry->interface);
					return ;
				}
			}
		}

		/* send packet through default gateway */
		{
			entry = sr->routing_table;
			ip_hdr->ip_ttl--;
			ip_hdr->ip_dst = entry->gw;
			set_ip_hdr(packet, ip_hdr);
			sr_send_packet(sr, packet, len, entry->interface);
		}
	}
	return ;
}

void sr_handle_icmp_packet(struct sr_instance* sr, unsigned int len, char *interface, struct sr_icmphdr *icmphdr, uint8_t *packet)
{
	struct ip *ip_hdr = get_ip_hdr(packet);
	struct sr_if* iface = sr_get_interface(sr, interface);
	char *src = inet_ntoa(ip_hdr->ip_src);
	char *dst = inet_ntoa(ip_hdr->ip_dst);

	if((icmphdr->icmp_type == (0x03 || 0x04 || 0x05 || 0x0B || 0x0C)) || (strcmp(dst, "0.0.0.0") == 0) || (strcmp(dst, "127.0.0.0") == 0))
	{   Debug("Cant create icmp");
		printf("ICMP error message can't be generated.");
		sr_route_packet(sr, packet, len, interface);
		return ;
	}



	/* echo request */
	if(icmphdr->icmp_type == 0x08)
	{
		if((iface->ip)==((ip_hdr->ip_dst).s_addr))
		{

			packet = create_icmp_msg(sr, packet, sr->routing_table->gw,ip_hdr->ip_src,len, interface, ICMP_TYPE_ECHO_REPLY, ICMP_CODE_ECHO_REPLY);
			sr_route_packet(sr, packet, len, interface);
		}
		else
		{
			Debug("Routing packet to app server\n");
			sr_route_packet(sr, packet, len, interface);
		}
	}

	/* echo reply */
	else if(icmphdr->icmp_type == 0x00)
	{ Debug("Its in reply\n");
		if((iface->ip)!=((ip_hdr->ip_dst).s_addr))
		{  Debug("I am sending  to sr route handle");
			sr_route_packet(sr, packet, len, interface);
		}
		else
		{
			printf("%d bytes from: to :%s  %s,   icmp_seq_num: %u,  ttl: %u", len,src,dst,icmphdr->icmp_seq, ip_hdr->ip_ttl);
		}
	}

	/* traceroute */
	else if(icmphdr->icmp_type == 0x1E && icmphdr->icmp_code == 0x00)
	{
		if((iface->ip)==((ip_hdr->ip_dst).s_addr))
		{
			icmphdr->icmp_rhc = 0x0000;
			inet_aton(src, &ip_hdr->ip_dst);
			inet_aton(dst, &ip_hdr->ip_src);
			set_ip_hdr(packet, ip_hdr);
			set_icmp_hdr(packet, icmphdr, ip_hdr);
			sr_route_packet(sr, packet, len, interface);
		}
		else
		{
			if(icmphdr->icmp_rhc == 0xFFFF)
				icmphdr->icmp_ohc++;
			else
				icmphdr->icmp_rhc++;
			set_icmp_hdr(packet, icmphdr, ip_hdr);
			sr_route_packet(sr, packet, len, interface);
		}
	}
	else
	{
		sr_route_packet(sr, packet, len, interface);
	}
}


void sr_handle_tcp_packet(struct sr_instance* sr, unsigned int len, char *interface, struct tcp *tcphdr, uint8_t *packet)
{
	struct ip *ip_hdr = get_ip_hdr(packet);
	uint8_t *error_packet = create_icmp_msg(sr,packet,sr->routing_table->gw, ip_hdr->ip_src, len,interface,ICMP_TYPE_DEST_UNREACHABLE,ICMP_CODE_DEST_PORT_UNREACHABLE);
	sr_route_packet(sr,error_packet,len,interface);
}

void sr_handle_udp_packet(struct sr_instance* sr, unsigned int len, char *interface, struct sr_udphdr *updhdr, uint8_t *packet)
{
	struct ip *ip_hdr = get_ip_hdr(packet);
	uint8_t *error_packet=create_icmp_msg(sr,packet,sr->routing_table->gw, ip_hdr->ip_src,len,interface,ICMP_TYPE_DEST_UNREACHABLE,ICMP_CODE_DEST_PORT_UNREACHABLE);
	sr_route_packet(sr,error_packet,len,interface);
}

void sr_handle_arp_packet(struct sr_instance* sr, unsigned int len, char *interface, struct
		sr_arphdr *arphdr, uint8_t *packet)
{
	assert(sr);
	struct sr_ethernet_hdr *eth_hdr = get_ethernet_hdr(packet);

	unsigned int if_num = (unsigned int)(*(interface + 3));
	if(arphdr->ar_op == ARP_REQUEST)
	{
		printf("ARP request recieved\n");
		sr_set_arp_cache_entry(sr, arphdr->ar_sip, arphdr->ar_sha, if_num);
		int i = 0;
		uint32_t destHost = arphdr->ar_tip;
		int destHostID = -1;
		for(i = 0; i < MAX_HOSTS && destHostID == -1; i = i + 1)
		{
			uint32_t currHost = sr->cacheHosts[i];
			/* Host has already has messages sent to it.*/
			if(currHost == destHost)
			{
				printf("Curr Host = %u\n",currHost);
				destHostID = i;
				/* struct sr_arp_cache_entry *destARPCacheEntry = sr->arp_cache[i]; */
				bool isStale = test_staleness(sr, i);
				int ackResponsiveness = sr->packetsSinceAck[i];
				if(isStale || ackResponsiveness >= MAX_SEND_PACKET)
				{
					Debug("The packet cache has become stale\n");
					struct in_addr dst;
					dst.s_addr = htonl(arphdr->ar_sip);
					uint8_t *error_packet = create_icmp_msg(sr, packet, sr->routing_table->gw, dst, IP_ICMP_LEN, interface, ICMP_TYPE_DEST_UNREACHABLE, ICMP_CODE_DEST_HOST_UNREACHABLE);
					/* send icmp unreachable host message to sender about destination */
					sr_route_packet(sr, error_packet, len, interface);
					sr_handle_staleness(sr, i);
				}
				/* send arp reply that all is well at this point */
				unsigned char cache_hdwr[ETHER_ADDR_LEN];
				int addr_pos;
				int false_addr = 1;
				for(addr_pos = 0; addr_pos < ETHER_ADDR_LEN; addr_pos++)
				{
					cache_hdwr[addr_pos] = sr->arp_cache[destHostID]->arp_dha[addr_pos];
					int addr_int = cache_hdwr[addr_pos];
					if(addr_int != 255)
					{
						false_addr = 0;
					}
				}
				if(false_addr == 0)
				{
					printf("Current Host in arp cache has mac addr = %s\n",cache_hdwr);
					uint32_t cache_ip = sr->arp_cache[destHostID]->arp_addr;
					uint8_t *arp_reply_packet = create_arp_reply(sr, cache_ip, cache_hdwr, arphdr->ar_sip, arphdr->ar_sha, ARP_REPLY);
					Debug("sending arp reply in response to arp request for information about non-stale host\n");
					sr_route_packet(sr,arp_reply_packet,(ETHER_HDR_LEN + ARP_HDR_LEN),interface);
					int currPacketCacheEntry;
					unsigned int dealtWithPacket = 0;
					for(currPacketCacheEntry = 0; currPacketCacheEntry < CACHE_SIZE && dealtWithPacket < 1; currPacketCacheEntry++)
					{
						int cacheEntryStatus = sr->packetCacheEntryStatus[destHostID][currPacketCacheEntry];
						if(cacheEntryStatus == 0)
						{
							insert_packet_into_arp_cache(sr, destHostID, currPacketCacheEntry, packet, len);
							dealtWithPacket = 1;
							sr->packetCacheEntryStatus[destHostID][currPacketCacheEntry] = 1;
							sr->packetsSinceAck[destHostID] = sr->packetsSinceAck[i] + 1;
						}
						else if(currPacketCacheEntry == CACHE_SIZE-1)
						{
							/* Clear cache of all packets for destination host */
							int j;
							for(j = 0; j < CACHE_SIZE; j = j + 1)
							{
								sr->packetCache[i][j] = 0;
								sr->packetCacheEntryStatus[i][j] = 0;
							}
							sr->timers[i] = clock();
							sr->packetsSinceAck[i] = 0;
							struct in_addr dst;
							dst.s_addr = htonl(arphdr->ar_sip);
							uint8_t *error_packet = create_icmp_msg(sr, packet, sr->routing_table->gw, dst, IP_ICMP_LEN, interface, ICMP_TYPE_DEST_UNREACHABLE, ICMP_CODE_DEST_HOST_UNREACHABLE);
							/* send icmp unreachable host message to sender about destination */
							sr_route_packet(sr, error_packet, len, interface);
							dealtWithPacket = 1;
						}
						if(dealtWithPacket > 0)
						{
							break;
						}
					}
				}
				else
				{
					printf("Sending ARP request because ARP cache entry has mac addr ff:ff:ff:ff:ff:ff\n");
					/* Set arp cache entry for sender */
					sr_set_arp_cache_entry(sr, arphdr->ar_sip, arphdr->ar_sha, if_num);
					sr->cacheHosts[i] = destHost;
					insert_packet_into_arp_cache(sr, destHostID, 0, packet, len);
					sr->packetCache[i][0] = packet;
					sr->timers[i] = clock();
					sr->packetsSinceAck[i] = 1;
					sr->packetCacheEntryStatus[i][0] = 1;
					/* send arp packet to destination */
					struct sr_arphdr *new_arphdr = create_arp_hdr(ARP_REPLY, arphdr->ar_sha, arphdr->ar_sip, arphdr->ar_tha, arphdr->ar_tip);
					set_arp_hdr(packet, new_arphdr);
					sr_route_packet(sr, packet, len, interface);
					break;
				}
			}
			else if(currHost == 0)
			{
				printf("Curr host = 0 and thus arp cache ip address for this entry is empty\n");
				destHostID = i;
				/* Set arp cache entry for sender */
				sr->cacheHosts[i] = arphdr->ar_sip;
				sr_set_arp_cache_entry(sr, arphdr->ar_sip, arphdr->ar_sha, if_num);
				sr->cacheHosts[i+1]= destHost;
				sr->timers[i] = clock();
				sr_set_arp_cache_entry(sr, arphdr->ar_tip, arphdr->ar_tha, if_num);
				insert_packet_into_arp_cache(sr, destHostID, 0, packet, len);
				sr->packetCache[i+1][0] = packet;
				sr->timers[i+1] = clock();
				sr->packetsSinceAck[i+1] = 1;
				sr->packetCacheEntryStatus[i+1][0] = 1;
				/* send arp packet to destination */
				struct sr_rt *entry;
				struct in_addr temp;
				temp.s_addr = arphdr->ar_tip;
				char *dst = inet_ntoa(temp);
				unsigned int msk;
				char *subnet;
				for(entry=sr->routing_table->next; entry!=NULL; entry=entry->next)
				{
					/*
					msk = (unsigned int)inet_ntoa(entry->mask);
					msk = entry->mask.s_addr;
					subnet = (unsigned int)inet_ntoa(entry->dest);
					 */
					subnet = inet_ntoa(entry->dest);
					if(strcmp(subnet,dst)==0)
					{

						struct sr_if *iface = sr_get_interface(sr,entry->interface);
						sr_set_arp_cache_entry(sr, arphdr->ar_sip, iface->addr, if_num);
						arphdr->ar_op = ARP_REPLY;
						int i;
						for(i=0; i<6;i++)
						{
							eth_hdr->ether_dhost[i] = eth_hdr->ether_shost[i];
							eth_hdr->ether_shost[i] = iface->addr[i];
							arphdr->ar_tha[i] = iface->addr[i];
						}
						arphdr->ar_sip = htonl(arphdr->ar_sip);
						arphdr->ar_tip = htonl(arphdr->ar_tip);
						set_arp_hdr(packet, arphdr);
						eth_hdr->ether_type = 0x0806;
						set_ethernet_hdr(packet, eth_hdr);
						sr_send_packet(sr, packet, len, entry->interface);
						return ;
					}
				}
				entry = sr->routing_table;
				/*arphdr->ar_tip = arphdr->ar_sip;*/
				arphdr->ar_sip = entry->gw.s_addr;
				printf("Did not find destination in routing table arp header sip = %u arp header tip = %u\n",arphdr->ar_tip,arphdr->ar_sip);
				memcpy(packet, eth_hdr, 14);
				set_arp_hdr(packet, arphdr);
				printf("sending out packet\n");
				sr_route_packet(sr, packet, len, interface);
				break;
			}
		}
		if(destHost == -1)
		{
			printf("Destination host not found in arp cache and no  entries in the arp cache\n");
			destHostID = i;
			/* Set arp cache entry for sender */
			sr_set_arp_cache_entry(sr, arphdr->ar_sip, arphdr->ar_sha, if_num);
			sr->cacheHosts[i] = arphdr->ar_sip;
			sr->packetCache[i][0] = packet;
			sr->timers[i] = clock();
			sr->packetsSinceAck[i] = 1;
			/* send arp packet to destination */
			struct sr_arphdr *new_arphdr = create_arp_hdr(arphdr->ar_op, arphdr->ar_sha, arphdr->ar_sip, arphdr->ar_tha, arphdr->ar_tip);
			set_arp_hdr(packet, new_arphdr);
			sr_route_packet(sr, packet, len, interface);
		}
	}
	else if(arphdr->ar_op == ARP_REPLY)
	{
		Debug("arp reply recv'd\n");
		int i = 0;
		uint32_t destHost = arphdr->ar_tip;
		int destHostID = -1;
		for(i = 0; i < MAX_HOSTS && destHostID == -1; i = i + 1)
		{
			uint32_t currHost = sr->cacheHosts[i];
			/* Host has already has messages sent to it.*/
			if(currHost == destHost)
			{
				destHostID = i;
				/* struct sr_arp_cache_entry *destARPCacheEntry = sr->arp_cache[i]; */
				bool isStale = test_staleness(sr, i);
				int ackResponsiveness = sr->packetsSinceAck[i];
				if(isStale || ackResponsiveness >= MAX_SEND_PACKET)
				{
					Debug("The packet cache has become stale\n");
					struct in_addr dst;
					dst.s_addr = htonl(arphdr->ar_sip);
					uint8_t *error_packet = create_icmp_msg(sr, packet, sr->routing_table->gw, dst, IP_ICMP_LEN, interface, ICMP_TYPE_DEST_UNREACHABLE, ICMP_CODE_DEST_HOST_UNREACHABLE);
					/* send icmp unreachable host message to sender about destination */
					sr_route_packet(sr, error_packet, len, interface);
					sr_handle_staleness(sr, i);
				}
				route_host_cache_head_packet(sr, destHostID);
			}
			else if(currHost == 0)
			{
				destHostID = i;
				/* Set arp cache entry for sender */
				sr_set_arp_cache_entry(sr, arphdr->ar_sip, arphdr->ar_sha, if_num);
				sr->cacheHosts[i] = destHost;
				insert_packet_into_arp_cache(sr, destHostID, 0, packet, len);
				sr->packetCache[i][0] = packet;
				sr->timers[i] = clock();
				sr->packetsSinceAck[i] = 1;
				sr->packetCacheEntryStatus[i][currHost] = 1;
				/* send arp packet to destination */
				struct sr_arphdr *new_arphdr = create_arp_hdr(arphdr->ar_op, arphdr->ar_sha, arphdr->ar_sip, arphdr->ar_tha, arphdr->ar_tip);
				set_arp_hdr(packet, new_arphdr);
				sr_route_packet(sr, packet, len, interface);
				break;
			}
		}
		if(destHost == -1)
		{
			destHostID = i;
			/* Set arp cache entry for sender */
			sr_set_arp_cache_entry(sr, arphdr->ar_sip, arphdr->ar_sha, if_num);
			sr->cacheHosts[i] = destHost;
			sr->packetCache[i][0] = packet;
			sr->timers[i] = clock();
			sr->packetsSinceAck[i] = 1;
			/* send arp packet to destination */
			struct sr_arphdr *new_arphdr = create_arp_hdr(arphdr->ar_op, arphdr->ar_sha, arphdr->ar_sip, arphdr->ar_tha, arphdr->ar_tip);
			set_arp_hdr(packet, new_arphdr);
			sr_route_packet(sr, packet, len, interface);
		}
	}
}

void insert_packet_into_arp_cache(struct sr_instance* sr, int destHostID, int currPacketCacheEntry,uint8_t* packet, unsigned int len)
{
	sr->packetCache[destHostID][currPacketCacheEntry] = (uint8_t *)malloc(len * sizeof(uint8_t));
	int i;
	for(i = 0; i < len; i++)
	{
		*(sr->packetCache[destHostID][currPacketCacheEntry] + i) = *(packet + i);
	}
}

void route_host_cache_head_packet(struct sr_instance* sr, int destHostID)
{
	uint8_t *headPacket;
	int j;
	for(j = 0; j < CACHE_SIZE; j++)
	{
		Debug("packetCache status for hostID# %i packet[%i] = %i\n",destHostID, j, sr->packetCacheEntryStatus[destHostID][j]);
	}
	if(sr->packetCacheEntryStatus[destHostID][0] == 1)
	{
		Debug("testing\n");
		struct sr_ethernet_hdr *eth_hdr = get_ethernet_hdr(sr->packetCache[destHostID][0]);
		unsigned int headPacketLen = 0;
		char *headPacketInterface = "";
		int j;
		for(j = 0; j < ETHER_ADDR_LEN; j++)
		{
			*(headPacketInterface+j) = (char)eth_hdr->ether_dhost[j];
		}
		if(htons(eth_hdr->ether_type) == ETHERTYPE_IP)
		{
			struct ip *ip_hdr = get_ip_hdr(sr->packetCache[destHostID][0]);
			headPacketLen = ETHER_HDR_LEN + ip_hdr->ip_len;
			Debug("Routing head packet to %s from %s", inet_ntoa(ip_hdr->ip_dst), inet_ntoa(ip_hdr->ip_src));
			sr_route_packet(sr, headPacket, headPacketLen, headPacketInterface);
			int currPacketCacheEntry;
			for(currPacketCacheEntry = 1; currPacketCacheEntry < CACHE_SIZE; currPacketCacheEntry++)
			{
				int cacheEntryStatus = sr->packetCacheEntryStatus[destHostID][currPacketCacheEntry];
				if(cacheEntryStatus == 1)
				{
					*(sr->packetCache[destHostID][currPacketCacheEntry-1]) = *(sr->packetCache[destHostID][currPacketCacheEntry]);
				}
			}
		}
		else if(htons(eth_hdr->ether_type) == ETHERTYPE_ARP)
		{
			struct sr_arphdr *arphdr;
			arphdr = get_arp_hdr(sr->packetCache[destHostID][0]);
			headPacketLen = ARP_HDR_LEN + ETHER_HDR_LEN;
			sr_route_packet(sr, headPacket, headPacketLen, headPacketInterface);
			int currPacketCacheEntry;
			for(currPacketCacheEntry = 1; currPacketCacheEntry < CACHE_SIZE; currPacketCacheEntry++)
			{
				int cacheEntryStatus = sr->packetCacheEntryStatus[destHostID][currPacketCacheEntry];
				if(cacheEntryStatus == 1)
				{
					*(sr->packetCache[destHostID][currPacketCacheEntry-1]) = *(sr->packetCache[destHostID][currPacketCacheEntry]);
				}
			}
		}
	}
}

uint32_t sr_get_host_ip_from_ether_addr(struct sr_instance* sr, unsigned char host_addr[])
{
	uint32_t host_ip = 0xffffffff;
	int i;
	for(i = 0; i < MAX_HOSTS; i++)
	{
		struct sr_arp_cache_entry *cache_entry = sr->arp_cache[i];
		if(strcmp(host_addr, cache_entry->arp_dha) == 0)
		{
			host_ip = cache_entry->arp_addr;
			i = MAX_HOSTS;
		}
	}
	return host_ip;
}


bool test_staleness(struct sr_instance* sr, unsigned int hostID)
{
	clock_t now = clock();
	clock_t staleness = (now - sr->timers[hostID]);
	if(sr->timers[hostID]==0)
	{
		return false;
	}
	else if(((double) staleness/CLOCKS_PER_SEC) > CACHE_SEC_TIMEOUT && sr->timers[hostID] != 0)
	{
		Debug("then = %i now = %i staleness = %i\n",sr->timers[hostID],now, staleness);
		return true;
	}
	return false;
}

void sr_handle_staleness(struct sr_instance* sr, unsigned int hostID)
{
	/* Clear cache of all packets for destination host */
	int j;
	for(j = 0; j < CACHE_SIZE; j = j + 1)
	{
		sr->packetCache[hostID][j] = 0;
		sr->packetCacheEntryStatus[hostID][j] = 0;
	}
	sr->timers[hostID] = clock();
	sr->packetsSinceAck[hostID] = 0;
}

void sr_set_arp_cache_entry(struct sr_instance* sr, uint32_t ip_addr, unsigned char hdw_addr[], unsigned int if_id)
{
	assert(sr);
	int ipID = sr_get_cache_host_id(sr, ip_addr);
	if(ipID == -1 || ipID == 0)
	{
		struct sr_arp_cache_entry *entry;
		entry = (struct sr_arp_cache_entry *)malloc(sizeof(struct sr_arp_cache_entry));
		entry->arp_addr = ip_addr;
		entry->arp_age = 0;
		int i;
		for(i = 0; i < ETHER_ADDR_LEN; i++)
		{
			entry->arp_dha[i] = hdw_addr[i];
		}
		entry->arp_if_id = if_id;
		sr->arp_cache[0] = entry;
		sr->cacheHosts[0] = ip_addr;
	}
	else{
		struct sr_arp_cache_entry *entry = sr->arp_cache[ipID];
		assert(entry);
		unsigned int age = 0;
		if(entry->arp_addr != 0)
		{
			clock_t now = clock();
			age = now - (sr->timers[ipID]);
			sr->timers[ipID] = now;
		}
		entry->arp_addr = ip_addr;
		entry->arp_age = age;
		int i;
		for(i = 0; i < ETHER_ADDR_LEN; i = i + 1)
		{
			entry->arp_dha[i] = hdw_addr[i];
		}
		entry->arp_if_id = if_id;
	}
}

int sr_get_cache_host_id(struct sr_instance* sr, uint32_t hostIP)
{
	int i;
	for(i = 0; i < MAX_HOSTS; i++)
	{
		/* Host has already has messages sent to it.*/
		if(sr->cacheHosts[i] == hostIP)
		{
			return i;
		}
		else if(sr->cacheHosts[i] == 0)
		{
			if(i == 0)
			{
				return -1;
			}
			return i;
		}
	}
	return -1;
}

/*---------------------------------------------------------------------
 * Method:
 *
 *---------------------------------------------------------------------*/

/* Given packet buffer, return ethernet header structure. */
struct sr_ethernet_hdr *get_ethernet_hdr(uint8_t *packet)
{
	assert(packet);
	struct sr_ethernet_hdr *eth_hdr;
	eth_hdr = (struct sr_ethernet_hdr *)malloc(sizeof(struct sr_ethernet_hdr));
	assert(eth_hdr);
	memcpy(eth_hdr, packet, sizeof(struct sr_ethernet_hdr));
	return eth_hdr;
}

struct sr_arphdr *get_arp_hdr(uint8_t *packet)
{
	struct sr_arphdr *arp_hdr;
	arp_hdr = (struct sr_arphdr *)malloc(sizeof(struct sr_arphdr));
	assert(packet);
	int i;
	uint8_t type0 = *(packet + ETHER_HDR_LEN);
	uint8_t type1 = *(packet + ETHER_HDR_LEN + 1);
	uint16_t type01 = ((uint16_t)type0 << 8) + ((uint16_t)type1);
	arp_hdr->ar_hrd = type01;
	type0 = *(packet + ETHER_HDR_LEN + 2);
	type1 = *(packet + ETHER_HDR_LEN + 3);
	type01 = ((uint16_t)type0 << 8) + ((uint16_t)type1);
	arp_hdr->ar_pro = type01;
	arp_hdr->ar_hln = *(packet + ETHER_HDR_LEN + 4);
	arp_hdr->ar_pln = *(packet + ETHER_HDR_LEN + 5);
	type0 = *(packet + ETHER_HDR_LEN + 6);
	type1 = *(packet + ETHER_HDR_LEN + 7);
	type01 = ((uint16_t)type0 << 8) + ((uint16_t)type1);
	arp_hdr->ar_op = type01;
	for(i = 0; i < ETHER_ADDR_LEN; i = i + 1)
	{
		arp_hdr->ar_sha[i] = *(packet + 8 + ETHER_HDR_LEN + i);
	}
	type0 = *(packet + 8 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
	type1 = *(packet + 9 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
	uint8_t type2 = *(packet + 10 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
	uint8_t type3 = *(packet + 11 + ETHER_ADDR_LEN + ETHER_HDR_LEN);
	uint32_t type0123 = ((uint32_t)type0 << 24) + ((uint32_t)type1 << 16) + ((uint32_t)type2 << 8) + ((uint32_t)type3);
	arp_hdr->ar_sip = type0123;
	for(i = 0; i < ETHER_ADDR_LEN; i++)
	{
		arp_hdr->ar_tha[i] = *(packet + 12 + ETHER_HDR_LEN + ETHER_ADDR_LEN  + i);
	}
	type0 = *(packet + 12 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN);
	type1 = *(packet + 13 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN);
	type2 = *(packet + 14 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN);
	type3 = *(packet + 15 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN);
	type0123 = ((uint32_t)type0 << 24) + ((uint32_t)type1 << 16) + ((uint32_t)type2 << 8) + ((uint32_t)type3);
	arp_hdr->ar_tip = type0123;
	assert(arp_hdr);
	/*	memcpy(arp_hdr, packet+sizeof(struct sr_ethernet_hdr), sizeof(struct sr_arphdr)); */
	return arp_hdr;
}

/* Given packet buffer, return ip header structure. */
struct ip *get_ip_hdr(uint8_t *packet)
{
	struct ip *hdr;
	hdr = (struct ip *)malloc(sizeof(struct ip));
	assert(hdr);
	memcpy(hdr, packet+sizeof(struct sr_ethernet_hdr), sizeof(struct ip));
	return hdr;
}

/* Given packet buffer, return icmp header structure. */
struct sr_icmphdr *get_icmp_hdr(uint8_t *packet)
{
	struct sr_icmphdr *hdr;
	struct ip *ip_hdr;
	ip_hdr = get_ip_hdr(packet);
	hdr = (struct sr_icmphdr *)malloc(sizeof(struct sr_icmphdr));
	assert(hdr);
	memcpy(hdr, packet+sizeof(struct sr_ethernet_hdr)+ip_hdr->ip_hl*4, sizeof(struct sr_icmphdr));
	return hdr;
}

/* Given packet buffer, return tcp header structure. */
struct tcp *get_tcp_hdr(uint8_t *packet)
{
	struct tcp *hdr;
	struct ip *ip_hdr;
	ip_hdr = get_ip_hdr(packet);
	hdr = (struct tcp *)malloc(sizeof(struct tcp));
	assert(hdr);
	memcpy(hdr, packet+sizeof(struct sr_ethernet_hdr)+ip_hdr->ip_hl*4, sizeof(struct tcp));
	return hdr;
}

/* Given packet buffer, return udp header structure. */
struct sr_udphdr *get_udp_hdr(uint8_t *packet)
{
	struct sr_udphdr *hdr;
	struct ip *ip_hdr;
	ip_hdr = get_ip_hdr(packet);
	hdr = (struct sr_udphdr *)malloc(sizeof(struct sr_udphdr));
	assert(hdr);
	memcpy(hdr, packet+sizeof(struct sr_ethernet_hdr)+ip_hdr->ip_hl*4, sizeof(struct sr_udphdr));
	return hdr;
}

void set_ethernet_hdr(uint8_t *packet, struct sr_ethernet_hdr *etherhdr)
{
	assert(packet);
	assert(etherhdr);
	int i;
	for(i = 0; i < ETHER_ADDR_LEN; i = i + 1)
	{
		*(packet+i) = etherhdr->ether_dhost[i];
		*(packet+ETHER_ADDR_LEN+i) = etherhdr->ether_shost[i];
	}
	uint8_t type0 = (uint8_t)etherhdr->ether_type;
	uint8_t type1 = (uint8_t)(etherhdr->ether_type >> 8);
	*(packet+(2*ETHER_ADDR_LEN)) = type1;
	*(packet+(2*ETHER_ADDR_LEN)+1) = type0;
}

void set_arp_hdr(uint8_t *packet, struct sr_arphdr *arphdr)
{
	assert(packet);
	assert(arphdr);
	uint8_t type0 = (uint8_t)arphdr->ar_hrd;
	uint8_t type1 = (uint8_t)(arphdr->ar_hrd >> 8);
	*(packet + ETHER_HDR_LEN) = type1;
	*(packet + ETHER_HDR_LEN+ 1) = type0;
	type0 = (uint8_t)arphdr->ar_pro;
	type1 = (uint8_t)(arphdr->ar_pro >> 8);
	*(packet + ETHER_HDR_LEN + 2) = type1;
	*(packet + ETHER_HDR_LEN+ 3) = type0;
	*(packet + ETHER_HDR_LEN + 4)  = arphdr->ar_hln;
	*(packet + ETHER_HDR_LEN + 5) = arphdr->ar_pln;
	type0 = (uint8_t)arphdr->ar_op;
	type1 = (uint8_t)(arphdr->ar_op >> 8);
	*(packet + ETHER_HDR_LEN + 6) = type1;
	*(packet + ETHER_HDR_LEN + 7) = type0;
	int i;
	for(i = 0; i < ETHER_ADDR_LEN; i++)
	{
		*(packet + ETHER_HDR_LEN + 8 + i)  = arphdr->ar_sha[i];
	}
	*(packet + 8 + ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_sip);
	*(packet + 9 + ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_sip >> 8);
	*(packet + 10 + ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_sip >> 16);
	*(packet + 11 + ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_sip >> 24);
	for(i = 0; i < ETHER_ADDR_LEN; i++)
	{
		*(packet + ETHER_HDR_LEN + ETHER_ADDR_LEN + 12 + i) = arphdr->ar_tha[i];
	}
	*(packet + 12 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_tip);
	*(packet + 13 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_tip >> 8);
	*(packet + 14 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_tip >> 16);
	*(packet + 15 + 2*ETHER_ADDR_LEN + ETHER_HDR_LEN) = (uint8_t)(arphdr->ar_tip >> 24);
	/*
	for(i = 0; i < 60; i++)
	{
		printf("%u ",*(packet + i));
	}
	printf("\n");
	 */
}

void set_ip_hdr(uint8_t *packet, struct ip *ip_hdr)
{
	int ether_hdr_len = 2*ETHER_ADDR_LEN + 2;
	uint8_t ip_hl_v;
#if __BYTE_ORDER == __LITTLE_ENDIAN
	ip_hl_v = ((uint8_t)(ip_hdr->ip_hl)<<4) + (ip_hdr->ip_v);
#elif __BYTE_ORDER == __BIG_ENDIAN
	ip_hl_v = ((uint8_t)(ip_hdr->ip_v)<<4) + (ip_hdr->ip_hl);
#endif
	*(packet + ether_hdr_len) = ip_hl_v;
	*(packet + ether_hdr_len + 1) = ip_hdr->ip_tos;
	uint8_t part0 = (uint8_t)ip_hdr->ip_len;
	uint8_t part1 = (uint8_t)(ip_hdr->ip_len >> 8);
	*(packet + ether_hdr_len + 2) = part1;
	*(packet + ether_hdr_len + 3) = part0;
	part0 = (uint8_t)ip_hdr->ip_id;
	part1 = (uint8_t)(ip_hdr->ip_id >> 8);
	*(packet + ether_hdr_len + 4) = part1;
	*(packet + ether_hdr_len + 5) = part0;
	part0 = (uint8_t)ip_hdr->ip_off;
	part1 = (uint8_t)(ip_hdr->ip_off >> 8);
	*(packet + ether_hdr_len + 6) = part1;
	*(packet + ether_hdr_len + 7) = part0;
	*(packet + ether_hdr_len + 8) = ip_hdr->ip_ttl;
	*(packet + ether_hdr_len + 9) = ip_hdr->ip_p;
	part0 = (uint8_t)ip_hdr->ip_sum;
	part1 = (uint8_t)(ip_hdr->ip_sum >> 8);
	*(packet + ether_hdr_len + 10) = part1;
	*(packet + ether_hdr_len + 11) = part0;
	uint32_t src_int = inet_addr(inet_ntoa(ip_hdr->ip_src));
	part0 = (uint8_t)(src_int);
	part1 = (uint8_t)(src_int>>8);
	uint8_t part2 = (uint8_t)(src_int>>16);
	uint8_t part3 = (uint8_t)(src_int>>24);
	*(packet + ether_hdr_len + 12) = part3;
	*(packet + ether_hdr_len + 13) = part2;
	*(packet + ether_hdr_len + 14) = part1;
	*(packet + ether_hdr_len + 15) = part0;
	uint32_t dst_int = inet_addr(inet_ntoa(ip_hdr->ip_dst));
	part0 = (uint8_t)(dst_int);
	part1 = (uint8_t)(dst_int>>8);
	part2 = (uint8_t)(dst_int>>16);
	part3 = (uint8_t)(dst_int>>24);
	*(packet + ether_hdr_len + 16) = part3;
	*(packet + ether_hdr_len + 17) = part2;
	*(packet + ether_hdr_len + 18) = part1;
	*(packet + ether_hdr_len + 19) = part0;
}

void set_icmp_hdr(uint8_t *packet, struct sr_icmphdr *icmphdr, struct ip *ip_hdr)
{
	unsigned int ip_len = ip_hdr->ip_len;
	*(packet + ip_len) = icmphdr->icmp_type;
	*(packet + ip_len + 1) = icmphdr->icmp_code;
	uint8_t part0 = (uint8_t)icmphdr->icmp_sum;
	uint8_t part1 = (uint8_t)(icmphdr->icmp_sum >> 8);
	*(packet + ip_len + 2) = part1;
	*(packet + ip_len + 3) = part0;
	part0 = (uint8_t)icmphdr->icmp_id;
	part1 = (uint8_t)(icmphdr->icmp_id >> 8);
	*(packet + ip_len + 4) = part1;
	*(packet + ip_len + 5) = part0;
	part0 = (uint8_t)icmphdr->icmp_seq;
	part1 = (uint8_t)(icmphdr->icmp_seq >> 8);
	*(packet + ip_len + 6) = part1;
	*(packet + ip_len + 7) = part0;
	part0 = (uint8_t)icmphdr->icmp_ohc;
	part1 = (uint8_t)(icmphdr->icmp_ohc >> 8);
	*(packet + ip_len + 8) = part1;
	*(packet + ip_len + 9) = part0;
	part0 = (uint8_t)icmphdr->icmp_rhc;
	part1 = (uint8_t)(icmphdr->icmp_rhc >> 8);
	*(packet + ip_len + 10) = part1;
	*(packet + ip_len + 11) = part0;
}

struct ip *create_ip(unsigned int hl, unsigned int v, uint8_t tos, uint16_t id, uint8_t p,
		struct in_addr src, struct in_addr dst, uint16_t len)
{
	struct ip *ip_packet;
	ip_packet = (struct ip *)malloc(sizeof(struct ip));
	assert(ip_packet);
	ip_packet->ip_hl = hl;
	ip_packet->ip_v = v;
	ip_packet->ip_tos = tos;
	ip_packet->ip_len = len;
	ip_packet->ip_id = id;
	ip_packet->ip_off = 0x0000;
	ip_packet->ip_ttl = INIT_TTL;
	ip_packet->ip_p = p;
	uint16_t buf[] = {(uint16_t)hl, (uint16_t)v, (uint16_t)tos, len, id, INIT_TTL, (uint16_t)p};
	uint16_t buf_len = 7;
	ip_packet->ip_sum = calculate_checksum(buf_len, buf);
	ip_packet->ip_src = src;
	ip_packet->ip_dst = dst;
	return ip_packet;
}

struct sr_ethernet_hdr *create_ethernet_header(uint8_t dhost[], uint8_t shost[], uint16_t type)
{
	struct sr_ethernet_hdr *etherhdr;
	etherhdr = (struct sr_ethernet_hdr*)malloc(sizeof(struct sr_ethernet_hdr));
	assert(etherhdr);
	int i;
	for(i = 0; i < ETHER_ADDR_LEN; i = i + 1)
	{
		etherhdr->ether_dhost[i] = dhost[i];
		etherhdr->ether_shost[i] = shost[i];
	}
	etherhdr->ether_type = type;
	return etherhdr;
}

struct sr_icmphdr *create_icmp_header(uint8_t type, uint8_t code, uint16_t id,uint16_t seq, uint16_t ohc, uint16_t rhc)
{
	struct sr_icmphdr *icmp_hdr;
	icmp_hdr = (struct sr_icmphdr *)malloc(sizeof(struct sr_icmphdr));
	assert(icmp_hdr);
	icmp_hdr->icmp_type = type;
	icmp_hdr->icmp_code = code;
	uint16_t sum = icmp_checksum(type, code, id, seq);
	icmp_hdr->icmp_sum = sum;
	icmp_hdr->icmp_id = id;
	icmp_hdr->icmp_seq = seq;
	icmp_hdr->icmp_ohc = ohc;
	icmp_hdr->icmp_rhc = rhc;
	return icmp_hdr;
}

struct tcp *create_tcp_hdr(uint16_t src_port, uint16_t dest_port, uint32_t seq, uint32_t ack, uint8_t flags, uint16_t win)
{
	struct tcp *tcp_hdr;
	tcp_hdr=(struct tcp *)malloc(sizeof(struct tcp));
	assert(tcp_hdr);
	tcp_hdr->tcp_source = src_port;
	tcp_hdr->tcp_dest=dest_port;
	tcp_hdr->tcp_seq_num=seq;
	tcp_hdr->tcp_ack_num=ack;
	tcp_hdr->tcp_window=win;
	uint16_t len_header = 10;
	uint16_t buff[len_header];
	buff[0] = src_port;
	buff[1] = dest_port;
	uint16_t high_seq = seq >>= 16;
	buff[2] = high_seq;
	uint16_t low_seq = (seq & 0xffff);
	buff[3] = low_seq;
	uint16_t high_ack = ack >>= 16;
	buff[4] = high_ack;
	uint16_t low_ack = (ack & 0xffff);
	buff[5] = low_ack;
	uint16_t flags_16 = (flags & 0xffff);
	buff[6] = flags_16;
	buff[7] = win;
	uint16_t chksum = calculate_checksum(len_header, buff);
	tcp_hdr->tcp_sum=chksum;
	return tcp_hdr;
}

struct sr_udphdr *create_udp_hdr(uint16_t src_port,uint16_t dest_port,uint16_t len)
{
	struct sr_udphdr *udp_hdr;
	udp_hdr=(struct sr_udphdr *)malloc(sizeof(struct sr_udphdr));
	assert(udp_hdr);
	udp_hdr->udp_src_port=src_port;
	udp_hdr->udp_dest_port=dest_port;
	udp_hdr->udp_len=len;
	uint16_t buff[] = {src_port, dest_port, len};
	uint16_t chksum = calculate_checksum(len, buff);
	udp_hdr->udp_sum=chksum;
	return udp_hdr;
}

struct sr_arphdr *create_arp_hdr(unsigned short arp_type, unsigned char send_hard_addr[], uint32_t send_ip, unsigned char targ_hard_addr[], uint32_t targ_ip)
{
	struct sr_arphdr *arp_hdr;
	arp_hdr=(struct sr_arphdr *)malloc(sizeof(struct sr_arphdr));
	assert(arp_hdr);
	arp_hdr->ar_hrd = ARPHDR_ETHER;
	arp_hdr->ar_pro = ETHERTYPE_ARP;
	arp_hdr->ar_hln = ETHER_ADDR_LEN;
	arp_hdr->ar_pln = IP_VERSION;
	arp_hdr->ar_op = arp_type;
	int i;
	for(i = 0; i < ETHER_ADDR_LEN; i = i + 1)
	{
		arp_hdr->ar_sha[i] = send_hard_addr[i];
		arp_hdr->ar_tha[i] = targ_hard_addr[i];
	}
	arp_hdr->ar_sip = send_ip;
	arp_hdr->ar_tip = targ_ip;
	return arp_hdr;
}


uint16_t calculate_checksum(uint16_t len_header, uint16_t buff[])
{
	uint16_t word16;
	uint32_t sum=0;
	uint16_t i;

	/* make 16 bit words out of every two adjacent 8 bit words in the packet
		 and add them up */
	for (i=0;i<len_header;i=i+2){
		word16 =((buff[i]<<8)&0xFF00)+(buff[i+1]&0xFF);
		sum = sum + (uint32_t) word16;
	}

	/* take only 16 bits out of the 32 bit sum and add up the carries */
	while (sum>>16)
		sum = (sum & 0xFFFF)+(sum >> 16);

	/* one's complement the result */
	sum = ~sum;

	return ((uint16_t) sum);
}

uint16_t icmp_checksum( uint8_t type,uint8_t code,uint16_t id,uint16_t seq)
{
	register uint16_t sum;
	uint16_t comp = 0xFF;
	sum = (( ((type^comp)&(code^comp)) & ((id^comp) &(seq^comp)) )^comp);
	return ~sum;
}

uint8_t *create_icmp_msg(struct sr_instance *sr, uint8_t *packet, struct in_addr src, struct in_addr dst, unsigned int len, char *interface, uint8_t type, uint8_t code)
{
	uint8_t *error_packet;
	error_packet = (uint8_t *)malloc(len*sizeof(uint8_t));
	assert(error_packet);
	struct sr_ethernet_hdr *old_etherhdr = get_ethernet_hdr(packet);
	int i;
	uint8_t dhost[ETHER_ADDR_LEN];
	uint8_t shost[ETHER_ADDR_LEN];
	char * shost_chr = get_hardware_address(sr, dst);
	for(i = 0; i < ETHER_ADDR_LEN; i = i + 1)
	{
		dhost[i] = old_etherhdr->ether_shost[i];
		shost[i] = *(shost_chr + i);
	}
	struct sr_ethernet_hdr *etherhdr = create_ethernet_header(dhost, shost, ETHERTYPE_IP);
	struct sr_icmphdr *unreachable_icmphdr = create_icmp_header(type, code, 0, 0, 0, 0xFFFF);
	struct ip *ip_hdr = create_ip(IP_HDR_LEN, IP_VERSION, IP_DEFAULT_TOS, IP_NON_FRAG_ID, IP_ICMP_PROTOCOL,src, dst, len);
	set_ethernet_hdr(error_packet, etherhdr);
	set_ip_hdr(error_packet, ip_hdr);
	set_icmp_hdr(error_packet, unreachable_icmphdr, ip_hdr);
	return error_packet;
}

uint8_t *create_arp_reply(struct sr_instance *sr, uint32_t src_ip,  unsigned char src_hdwr[], uint32_t targ_ip, unsigned char targ_hdwr[], unsigned short op)
{
	uint8_t *reply_packet;
	reply_packet = (uint8_t *)malloc((ARP_HDR_LEN + ETHER_HDR_LEN)*sizeof(uint8_t));
	assert(reply_packet);
	struct sr_ethernet_hdr *etherhdr = create_ethernet_header(targ_hdwr,src_hdwr,ETHERTYPE_ARP);
	struct sr_arphdr *arphdr = create_arp_hdr(op, src_hdwr,src_ip,targ_hdwr,targ_ip);
	set_ethernet_hdr(reply_packet,etherhdr);
	set_arp_hdr(reply_packet,arphdr);
	return reply_packet;
}

void sr_init_arp_cache(struct sr_instance *sr)
{
	assert(sr);
	struct sr_if* if_walker = 0;
	if_walker = sr->if_list;
	while(if_walker)
	{
		struct sr_arp_cache_entry *interfaceARPCacheEntry;
		interfaceARPCacheEntry = (struct sr_arp_cache_entry *)malloc(sizeof(struct sr_arp_cache_entry));
		assert(interfaceARPCacheEntry);
		interfaceARPCacheEntry->arp_addr = if_walker->ip;
		interfaceARPCacheEntry->arp_age = 0;
		struct in_addr temp_addr;
		temp_addr.s_addr = if_walker->ip;
		int i;
		for(i = 0; i < ETHER_ADDR_LEN; i++)
		{
			interfaceARPCacheEntry->arp_dha[i] = if_walker->addr[i];
		}
		sr->arp_cache[i] = interfaceARPCacheEntry;
		if_walker = if_walker->next;
	}
	Debug("Initialized the ARP cache with router's interfaces\n");
}
